import java.util.PriorityQueue;

public class 滑动窗口最大值 {
    // 暴力做法, 最后两个无法通过
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 找出返回值的大小
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int cnt = 0;
        // 滑动窗口预备
        int left = 0;
        // 0 为索引 1为大小
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> {
            if (a[1] > b[1]) {
                return b[0] - a[0];
            } else {
                return b[0] - a[0];
            }
        });
        for (int right = 0; right < n; right++) {
            heap.offer(new int[]{right,nums[right]});
            if (right - left + 1 == k) {
                while (!(heap.peek()[0] >= left && heap.peek()[0] <= right)) {
                    heap.poll();
                }
                ans[cnt++] = heap.peek()[1];
            }
        }
        return ans;
    }

    private int find(int[] nums, int left, int right) {
        int ret = nums[left];
        for (int i = left + 1; i <= right; i++) {
            ret = Math.max(ret,nums[i]);
        }
        return ret;
    }

    // 堆来维护
    public int[] maxSlidingWindow1(int[] nums, int k) {
        // 找出返回值的大小
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int cnt = 0;
        // 滑动窗口预备
        int left = 0;
        // 0 为索引 1为大小
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> {
            return b[1] != a[1] ? b[1] - a[1] : a[0] - b[0];
        });
        for (int right = 0; right < n; right++) {
            heap.offer(new int[]{right,nums[right]});
            if (right - left + 1 == k) {
                while (!(heap.peek()[0] >= left && heap.peek()[0] <= right)) {
                    heap.poll();
                }
                left++;
                ans[cnt++] = heap.peek()[1];
            }
        }
        return ans;
    }
}
